package wtx.leetcode;
class Solution1 {
  class RangeLink {
    AssendingRange head;
    AssendingRange current;
    RangeLink() {
      head = new AssendingRange();
      current = head;
    }

    AssendingRange next() {
      if (current.next != null) {
        AssendingRange r = current.next;
        current = current.next;
        return r;
      } else {
        return null;
      }
    }
    int size() {
      int i = 0;
      resetFromHead();
      while(hasNext()) {
        ++i;
        next();
      }
      resetFromHead();
      return i;
    }
    RangeLink add(AssendingRange r) {
      current.next = new AssendingRange(r);
      current = current.next;
      return this;
    }

    void resetFromHead() {
      current = head;
    }

    boolean hasNext() {
      return current.next != null;
    }
    boolean removeAfter(AssendingRange r) {
      if (r.next != null) {
        AssendingRange nextRange = r.next;
        r.next = nextRange.next;
        return true;
      } else {
        return false;
      }
    }
  }
  class AssendingRange {
    int start; 
    int end;  
    int buy; // prices[buy] is buy price
    int sell;// prices[sell] is sell price
    AssendingRange next = null;
    AssendingRange() {
      this.start = -1;
      this.end = -1;
      this.buy = -1;
      this.sell = -1;
    }

    AssendingRange(AssendingRange other) {
      this.start = other.start;
      this.end = other.end;
      this.buy = other.buy;
      this.sell = other.sell;
      this.next = other.next;
    }
    AssendingRange setStart(int s) {
      this.start = s;
      return this;
    }

    AssendingRange setEnd(int p) {
      this.end = p;
      return this;
    }
    
    AssendingRange setBuy(int s) {
      this.buy = s;
      return this;
    }

    AssendingRange setSell(int p) {
      this.sell = p;
      return this;
    }

    AssendingRange setNext(AssendingRange r) {
      this.next = r;
      return this;
    }
    int profit(int[] prices) {
      if (buy >= 0 && sell >= 0) {
        return prices[sell] - prices[buy];
      } else {
        return 0;
      }
    }
  }

  RangeLink rangeLink;

  private void initAssendRangeArray(int prices[]) {
    rangeLink = new RangeLink();
    int start = 0;
    int last = 0;
    for (int i = 1; i < prices.length; ++i) {
      if (prices[i] <= prices[last]) {
        if (i - start > 1) {
          rangeLink.add(new AssendingRange()
            .setStart(start)
            .setEnd(i)
            .setBuy(start)
            .setSell(last));
        }
        start = i;
        last = i;
      } else {
        last = i;
      }
    }
    if (last - start > 0) {
      rangeLink.add(new AssendingRange()
        .setStart(start)
        .setEnd(last+1)
        .setBuy(start)
        .setSell(last)
      );
    }
    rangeLink.resetFromHead();
  }

  private void mergeAssendings(int[] prices) {
    // find least loss for profit
    AssendingRange startRange = null;
    AssendingRange nextRange = null;
    AssendingRange mergedRange = null;
    AssendingRange insertPos = null;
    rangeLink.resetFromHead();
    startRange = rangeLink.next();
    int minLoss = Integer.MAX_VALUE;
    while (rangeLink.hasNext()) {
      nextRange = rangeLink.next();
      // try merge
      AssendingRange merged = mergeRangePairs(startRange, nextRange, prices);
      int loss = startRange.profit(prices) + nextRange.profit(prices) - merged.profit(prices);
      if (minLoss > loss) {
        minLoss = loss;
        mergedRange = merged;
        insertPos = startRange;
      }
      startRange = nextRange;
    }
    insertPos.setBuy(mergedRange.buy)
          .setSell(mergedRange.sell)
          .setStart(mergedRange.start)
          .setEnd(mergedRange.end)
          .setNext(mergedRange.next);
    rangeLink.resetFromHead();
  }

  private AssendingRange mergeRangePairs(AssendingRange start, AssendingRange end, int[] prices) {
    AssendingRange merged = new AssendingRange(start);
    merged.setEnd(end.end).setNext(end.next);
    if (prices[end.sell] > prices[start.sell]) {
      merged.setSell(end.sell);
      if (prices[end.buy] < prices[start.buy]) {
        merged.setBuy(end.buy);
      }
    } else {
      if (start.profit(prices) < end.profit(prices)) {
        merged = new AssendingRange(end);
        merged.setStart(start.start);
      }
    }
    return merged;
  }
  public int maxProfit(int k, int[] prices) {
    if (prices == null) return 0;
    if (k < 1) return 0;
    int maxK = k;
    if (prices.length / 2 < k) {
      maxK = prices.length/2;
    }
    initAssendRangeArray(prices);
    while(rangeLink.size() > maxK) {
      mergeAssendings(prices);
    }
    int profit = 0;
    rangeLink.resetFromHead();
    for (;rangeLink.hasNext();) {
      AssendingRange r = rangeLink.next();
      profit += r.profit(prices);
    }
    return profit;
  }
}